public class 最长上升子序列_dp {
    /*
    https://www.nowcoder.com/practice/5164f38b67f846fb8699e9352695cd2f?tpId=196&ru=%2Fexam%2Foj&difficulty=&judgeStatus=&tags=&title=&sourceUrl=&gioEnter=menu
     */
    public int LIS (int[] arr) {
        // write code here
        int n = arr.length;
        int[] dp = new int[n];
        int ret = 0;
        for(int i = 0;i < n;i++){
            for(int j = i;j >= 0;j--){
                if(arr[i] >= arr[j]){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
                ret = Math.max(ret,dp[i]);
            }
        }
        return ret;
    }
}
